package seminarski.geometrija;

import java.util.LinkedList;
import java.util.Queue;

import seminarski.utils.Utils;
import utils.AnalyticGeometries;

import common.point.PointG;
import common.segment.SegmentG;

public class Traka {
	ConvexHull hull;
	SegmentG<Double> segment;
	SegmentG<Double> oldSegment, oldSegment1;
	PointG<Double> point;
	PointG<Double> oldPoint;
	private Queue<Trio<PointG<Double>, SegmentG<Double>>> queue;

	public Traka(ConvexHull convexHull) {
		this.hull = convexHull;
		queue = new LinkedList<Trio<PointG<Double>, SegmentG<Double>>>();
	}
	
	public void findUgaonaTraka(){
		queue.clear();
		System.out.println(hull.hullSize());
		int n = hull.hullSize();
		int imin, imax;
		PointG<Double> min, max;
		SegmentG<Double> pmin, pmax;
		double k, nmin, nmax;
		double alfamin, alfamax;
		double distance1 = 0, distance2 = 0;
		imin = Utils.getMinY(hull.getHull());
		min = hull.getPoint(imin);
		if (imin == n || imin == n - 1 || imin == n - 2) {
			imax = n / 2;
			max = hull.getPoint(imax);
		} else {
			imax = 0;
			max = hull.getPoint(0);
		}
		k = 0;
		nmin = min.y();
		nmax = max.y();
		pmin = newSegment(min, k, nmin);
		pmax = newSegment(max, k, nmax);
		enqueue(pmin, pmax, max);
		distance1 = parallelLinesDistance(k, nmin, nmax);
		int i = 0;
		do{
			int imin2 = (imin - 1) % n;
			int imax2 = (imax - 1) % n;
			if(imin2 < 0)
				imin2 = n + imin2;
			if(imax2 < 0)
				imax2 = n + imax2;
			alfamin = Math.atan(tg(k, nadjiK(hull.getPoint(imin), hull.getPoint(imin2))));
			alfamax = Math.atan(tg(k, nadjiK(hull.getPoint(imax), hull.getPoint(imax2))));
			if(alfamax <= alfamin){
				pmax = new SegmentG<Double>(max, hull.getPoint(imax2));
				k = nadjiK(pmax.p1(), pmax.p2());
				nmax = nadjiN(k, max);
				imax = (imax - 1) % n;
				if(imax < 0)
					imax = n + imax;
				max = hull.getPoint(imax);
				nmin = nadjiN(k, min);
				pmin = newSegment(min, k, nmin);
				if(!presek(hull, pmin, imax2, false)){
					enqueue(pmin, min, pmax, k, nmax);
				}
					
			}else{
				pmin = new SegmentG<Double>(min, hull.getPoint(imin2));
				k = nadjiK(pmin.p1(), pmin.p2());
				nmin = nadjiN(k, min);
				imin = (imin - 1) % n;
				if(imin < 0)
					imin = n + imin;
				min = hull.getPoint(imin);
				nmax = nadjiN(k, max);					
				pmax = newSegment(max, k, nmax);
				if(!presek(hull, pmax, imax2, false)){
					enqueue(pmax, max, pmin, k, nmin);
				}
					
			}
			distance2 = distance1; 
			distance1 = parallelLinesDistance(k, nmin, nmax);
//			i ++;
		}while(distance2 >= distance1);
		System.out.println(queue.size()+ "\n");
	}

	private void enqueue(SegmentG<Double> pmax, SegmentG<Double> pmin,
			PointG<Double> min) {
		queue.add(new Trio<PointG<Double>, SegmentG<Double>>(min, pmin, pmax));
	}

	private double tg(double k1, double k2) {		
		return Math.abs((k1 - k2)/(1 + k1*k2));
	}

	public void findTraka() {
		int n = hull.hullSize();
		int indeksMax, indeks1 = 0, indeks2 = 0, indeks3 = 0;
		PointG<Double> max = null;
		int indeksMin = Utils.getMinY(hull.getHull());
		PointG<Double> min = hull.getPoint(indeksMin);
		max = hull.getPoint(0);
		double k = 0, kPetlje = -1.0;
		double n1 = min.y();
		double n2 = max.y(), n2Petlje = -1.0, n1Petlje = -1.0;
		double rastojanjePetlje = -1.0;
		double rastojanje = parallelLinesDistance(k, n1, n2);
		double rastojanje2 = rastojanje;
		if (indeksMin == n || indeksMin == n - 1 || indeksMin == n - 2) {
			indeksMax = n / 2;
			max = hull.getPoint(indeksMax);
		} else {
			indeksMax = 0;
			max = hull.getPoint(0);
		}
		SegmentG<Double> segmentPetlje = null;
		PointG<Double> pointPetlje = null;
		enqueueHorizontalne(min, hull.getPoint(0));
		if(hull.hullSize() == 2)
		{
			queue.add(new Trio<PointG<Double>, SegmentG<Double>>(min, new SegmentG<Double>(new PointG<Double>(0.0, min.y()), 
					new PointG<Double>(500.0, min.y())), 
					new SegmentG<Double>(new PointG<Double>(0.0, max.y()), 
							new PointG<Double>(500.0, max.y()))));
			return;
		}
		if(hull.hullSize() == 3){
			nadjiUTrouglu(hull);
			return;
		}
		for (int j = 0; j < hull.hullSize(); j++) {
//			System.out.println("j = " + j);
			rastojanjePetlje = -1.0;
			for (int i = 0; i < 4; i++) {

				if (i == 0) {
					indeks1 = indeksMin;
					indeks2 = (indeksMin + 1) % n;
					indeks3 = indeksMax;
				}
				if (i == 1) {
					indeks1 = indeksMin;
					indeks2 = (indeksMin - 1) % n;
					if (indeks2 < 0)
						indeks2 = n + indeks2;
					indeks3 = indeksMax;

				}
				if (i == 2) {
					indeks1 = indeksMax;
					indeks2 = ((indeksMax - 1) % n);
					if (indeks2 < 0)
						indeks2 = n + indeks2;
					indeks3 = indeksMin;
				}
				if (i == 3) {
					indeks1 = indeksMax;
					indeks2 = ((indeksMax + 1) % n);
					indeks3 = indeksMin;
				}

				if (indeks1 == indeks3 || indeks2 == indeks3) {
					indeks3 = (indeks1 + n / 2) % n;
				}
				segment = new SegmentG<Double>(hull.getPoint(indeks1), hull
						.getPoint(indeks2));
				point = hull.getPoint(indeks3);
				k = nadjiK(segment.p1(), segment.p2());
				n1 = nadjiN(k, segment.p1());
				n2 = nadjiN(k, point);
				if (presek(hull, new SegmentG<Double>(point,
						new PointG<Double>((double) indeksMax,
								(k * indeksMax + n2))), i, false)) {
					continue;
				} else {
					rastojanje = parallelLinesDistance(k, n1, n2);

					if (rastojanjePetlje == -1.0) {
						rastojanjePetlje = rastojanje;
						pointPetlje = point;
						segmentPetlje = segment;
						kPetlje = k;
						n2Petlje = n2;
						n1Petlje = n1;
					} else if (rastojanjePetlje != -1.0
							&& rastojanjePetlje > rastojanje) {
						pointPetlje = point;// = pointPetlje;
						segmentPetlje = segment;// = segmentPetlje;
						rastojanjePetlje = rastojanje;
						kPetlje = k;
						n2Petlje = n2;
						n1Petlje = n1;
					}
					if (Double.isNaN(rastojanjePetlje))
						rastojanjePetlje = -1.0;

				}
			}
			if (rastojanjePetlje != -1.0) {
				rastojanje = rastojanjePetlje;
				SegmentG<Double> s1 = newSegment(pointPetlje, kPetlje, n2Petlje);
				enqueue(segmentPetlje, pointPetlje, s1, kPetlje, n2Petlje,
						n1Petlje);
//				System.out.println(rastojanjePetlje + " :: " + rastojanje2);
				if (rastojanjePetlje < rastojanje2) {
					rastojanje2 = rastojanjePetlje;
					oldPoint = pointPetlje;
					oldSegment = newSegment(segmentPetlje.p1(), kPetlje,
							n1Petlje);
					oldSegment1 = s1;

				}
			}
			indeksMax = (indeksMax + 1) % n;
			indeksMin = (indeksMin + 1) % n;
		}
		if(oldPoint != null)
			queue.add(new Trio<PointG<Double>, SegmentG<Double>>(oldPoint,
				oldSegment, oldSegment1));
	}
	private void enqueueHorizontalne(PointG<Double> min, PointG<Double> max) {
        SegmentG<Double> s1, s2;
        s1 = new SegmentG<Double>(
                        new PointG<Double>(0.0, max.y().doubleValue()),
                        new PointG<Double>(500.0, max.y().doubleValue()));
        s2 = new SegmentG<Double>(
                        new PointG<Double>(0.0, min.y().doubleValue()),
                        new PointG<Double>(500.0, min.y().doubleValue()));
        queue.add(new Trio<PointG<Double>, SegmentG<Double>>(max, s1, s2));

}

	private void nadjiUTrouglu(ConvexHull hull) {
		int indeks1, indeks2;
		double rastojanje, k, n1, n2;
		double rastojanjeMin = 0;//, kMin = 0, n1Min = 0, n2Min = 0;
		for(int i = 0; i < 3; i++){
			indeks1 = (i + 1) % 3;
			indeks2 = (i + 2) % 3;

			k = nadjiK(hull.getPoint(indeks1), hull.getPoint(indeks2));
			n1 = nadjiN(k, hull.getPoint(indeks1));
			n2 = nadjiN(k, hull.getPoint(i));
			rastojanje = parallelLinesDistance(k, n1, n2);		

			queue.add(new Trio<PointG<Double>, SegmentG<Double>>(hull.getPoint(i), 
					newSegment(hull.getPoint(indeks1), k, n1),
					newSegment(hull.getPoint(i), k, n2)));
			if(i == 0){
				rastojanjeMin = rastojanje;
				oldSegment = newSegment(hull.getPoint(indeks1), k, n1);
				oldSegment1 = newSegment(hull.getPoint(i), k, n2);
				oldPoint = hull.getPoint(i);
			}
			else if(rastojanjeMin > rastojanje)
			{
				rastojanjeMin = rastojanje;
				oldSegment = newSegment(hull.getPoint(indeks1), k, n1);
				oldSegment1 = newSegment(hull.getPoint(i), k, n2);
				oldPoint = hull.getPoint(i);
			}
		}
		queue.add(new Trio<PointG<Double>, SegmentG<Double>>(oldPoint, oldSegment1, oldSegment));
		
		
	}


	private SegmentG<Double> newSegment(PointG<Double> point, double k,
			double n2) {
		PointG<Double> p1, p2;
		p1 = new PointG<Double>(point.x().doubleValue() - 500.0, k
				* (point.x().doubleValue() - 500.0) + n2);
		p2 = new PointG<Double>(point.x().doubleValue() + 500.0, k
				* (point.x().doubleValue() + 500.0) + n2);
		p1 = checkPoint(p1, k, n2, false);
		p2 = checkPoint(p2, k, n2, true);

		SegmentG<Double> s = new SegmentG<Double>(p1, p2);

		return s;
	}

	private PointG<Double> checkPoint(PointG<Double> p, double k, double n,
			boolean sign) {
		double x = 500;
		double y = p.y();
		if (!(Double.isInfinite(y) || Double.isNaN(y)))
			return p;
		while (Double.isInfinite(y) || Double.isNaN(y)) {
			x--;
			if (!sign)
				y = k * (p.x().doubleValue() - x) + n;
			else
				y = k * (p.x().doubleValue() + x) + n;
		}
		p = new PointG<Double>(p.x().doubleValue() - x, k
				* (p.x().doubleValue() - x) + n);
		return p;
	}

	public void enqueue(SegmentG<Double> segment, PointG<Double> point,
			SegmentG<Double> s1, double k, double n2, double n1) {
		SegmentG<Double> s = newSegment(segment.p1(), k, n1);
		
		queue.add(new Trio<PointG<Double>, SegmentG<Double>>(
				new PointG<Double>(point.x().doubleValue(), point.y()
						.doubleValue()), s, s1));
	}

	public void enqueue(SegmentG<Double> s0, PointG<Double> point,
			SegmentG<Double> s1, double k, double n1) {
		SegmentG<Double> s2 = newSegment(s1.p1(), k, n1);
		
		queue.add(new Trio<PointG<Double>, SegmentG<Double>>(
				new PointG<Double>(point.x().doubleValue(), point.y()
						.doubleValue()), s0, s2));
	}
	private double nadjiN(double k, PointG<Double> p1) {
		return p1.y() - k * p1.x();
	}

	private double nadjiK(PointG<Double> p1, PointG<Double> p2) {
		return (p2.y() - p1.y()) / (p2.x() - p1.x());
	}

	public double parallelLinesDistance(double k, double n1, double n2) {
		return Math.abs(n2 - n1) / Math.sqrt(k * k + 1);
	}

	public ConvexHull getOmotac() {
		return hull;
	}

	public boolean presek(ConvexHull hull, SegmentG<Double> duz, int j, boolean smer) {
		PointG<Double> f;
		SegmentG<Double> a;
		int size = hull.hullSize() - 1;
		for (int i = 0; i < size; i++) {
			a = new SegmentG<Double>(hull.getPoint(i), hull.getPoint(i + 1));
			/* prvi parametar je paralelna duz, nju "produzava", drugu ne dira */
			if ((f = AnalyticGeometries.geometryGDoubleExact.intersection(duz,
					a)) != null) {
				if (hull.pointOnAHull(f)) {
					continue;
				}
				return true;
			}
		}
		/* provera za prvu i poslednju tacku na omotacu */
		a = new SegmentG<Double>(hull.getPoint(0), hull.getPoint(size));
		if ((f = AnalyticGeometries.geometryGDoubleExact.intersection(duz, a)) != null) {
			if (!hull.pointOnAHull(f)) {
				return true;
			}
		}

		return false;
	}

	public Queue<Trio<PointG<Double>, SegmentG<Double>>> getQueue() {
		return queue;
	}
}
